package 栈;

import common.GeneralFunction;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class No42接雨水 {

    /**
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     *
     *  
     *
     * 示例 1：
     *
     *
     *
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
     * 在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * 示例 2：
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     *  
     *
     * 提示：
     * n == height.length
     * 0 <= n <= 3 * 104
     * 0 <= height[i] <= 105
     */

    /**
     * 自己写的不行
     * 参考多种解法:
     * 1.按列求(解法基础)
     * 2.对1的升级,动态规划版
     * 3.对动态规划版的空间优化版
     * 4.单调栈
     */

    //解法一:按列求,求每一列的最高水位即可。(找到左右两边的最高柱子高度,然后最小的减当前柱子高度)
    public int trap1(int[] height) {

        if(height.length<3){
            return 0;
        }

        int result=0;

        for (int i = 1; i < height.length-1; i++) {

            int maxLeft=0;
            int maxRight=0;

            for (int j = i-1; j >= 0; j--) {
                maxLeft=Math.max(maxLeft,height[j]);
            }

            for (int j = i+1; j < height.length; j++) {
                maxRight=Math.max(maxRight,height[j]);
            }

            int minHeight=Math.min(maxLeft,maxRight);
            if(minHeight>height[i]) {
                result += minHeight-height[i];
            }

        }

        return result;
    }

    //解法二:解法一的动态规划版;因为一有重复的计算最高高度
    public int trap2(int[] height) {

        if(height.length<3){
            return 0;
        }

        //存0~left的Max
        int[] leftMaxDp=new int[height.length];
        //存right~height.length-1的Max
        int[] rightMaxDp=new int[height.length];

        //base
        leftMaxDp[0]=height[0];
        rightMaxDp[height.length-1]=height[height.length-1];

        for (int i = 1; i < height.length; i++) {
            leftMaxDp[i]=Math.max(height[i],leftMaxDp[i-1]);
        }

        for (int i = height.length-2; i >= 0; i--) {
            rightMaxDp[i]=Math.max(height[i],rightMaxDp[i+1]);
        }

        int result=0;

        for (int i = 1; i < height.length-1; i++) {

            int minHeight=Math.min(leftMaxDp[i],rightMaxDp[i]);
            if(minHeight>height[i]) {
                result += minHeight-height[i];
            }

        }

        return result;
    }

    //解法三:空间优化版;因为我们是向右遍历的,所以最左的Max高度就可以在我遍历过程中不断更新
    public int trap3(int[] height) {

        if(height.length<3){
            return 0;
        }

        int[] rightMaxDp=new int[height.length];
        rightMaxDp[height.length-1]=height[height.length-1];

        for (int i = height.length-2; i >= 0; i--) {
            rightMaxDp[i]=Math.max(rightMaxDp[i+1],height[i]);
        }

        int maxLeftHeight=height[0];
        int result=0;

        for (int i = 1; i < height.length - 1; i++) {

            maxLeftHeight=Math.max(maxLeftHeight,height[i]);
            int minHeight=Math.min(maxLeftHeight,rightMaxDp[i]);
            if(minHeight>height[i]){
                result+=minHeight-height[i];
            }

        }

        return result;
    }

    //解法四:单调栈
    public int trap4(int[] height) {

        if(height.length<3){
            return 0;
        }

        int sum = 0;
        int index=0;
        Deque<Integer> stack=new ArrayDeque<>();

        while (index<height.length){

            //不为空&&当前墙大于栈顶墙 (维护单调栈的性质)
            while (!stack.isEmpty()&&height[index]>height[stack.peekLast()]){

                //因为横向,所以要弹出一堵墙,弹出的就是中间的空位
                int lastIndex=stack.pollLast();
                if(stack.isEmpty()){
                    //就一堵墙,例如 [..,4,5,..] 栈中只有[4-5] 存不了水
                    break;
                }
                //min(右墙高度,左墙的高度)
                int minHeight=Math.min(height[index],height[stack.peekLast()]);
                //左右墙的之间的宽度
                int width=index-stack.peekLast()-1;
                //增加的高度=最低的高度-中间空位的高度
                int currentHeight=minHeight-height[lastIndex];
                /**
                 * 横向增加
                 */
                sum+=width*currentHeight;
            }
            /**
             * 单调栈,里面存的都是递减元素;栈顶的最小;
             */
            stack.addLast(index);
            index++;

        }


        return sum;
    }

    public static void main(String[] args) {

        int[] arr={5,4,3,2,6};
        GeneralFunction generalFunction=new GeneralFunction(No42接雨水.class,arr);
        generalFunction.runAllMethod();

    }

}
